1. Field of the Invention
This invention relates to data storage and more particularly relates to efficiently mapping virtual and physical addresses in a data storage device.
2. Description of the Related Art
Traditional data storage devices, such as disk drives, optical drives, etc. often operate as a random access device to store data. Random access is typically the ability to access an arbitrary element of a sequence in equal time. This differs from sequential access where data is stored sequentially and also accessed sequentially. For example, a tape for storing data is a sequential device. Accessing one data element can take a different amount of time since one data element may be located close to the where a read head is located and another data element may take longer to access because the tape must be forwarded or reversed to get to the second data element. A random access device, such as a memory chip, a disk drive, or solid-state storage, operates as a random access device because access time to every data element on the random access device requires approximately the same access time. Random access is desirable because of the predictable nature and efficiency of data access.
Typically, a file system communicates with a random access storage device using low level commands. The file system manages where the data is placed. The low level commands typically include a physical address and a data length in a command to store or access data. Data in a random access storage device may be updated typically in a read-modify-write operation where data at a particular address is read, modified, and then written to the same location where it was stored.
While the concept of a random access device is desirable, random access may cause problems in certain types of data storage. For example, random access may cause certain locations in the storage device to used much more than other locations. This aspect of random access may be detrimental in flash memory because typically each memory cell in flash memory can only be used a certain number of times before it must be reconditioned or becomes unreliable. Random access may also cause a storage device to become fragmented, which can increase storage access times.
Sequential storage for data storage device such as flash memory and other solid-state storage may be used to alleviate some of the problems associated with random access. Where sequential storage is used, it is often desirable to have some type of storage space recovery (garbage collection) system to consolidate valid data and free up regions of storage for sequential storage of data. Typically, a storage space recovery routine will encounter valid data in a region selected for recovery. The valid data is typically moved to another location prior to processing the selected region.
One way to identify valid data is to search the selected region to identify where the valid data is located in the selected region prior to moving the valid data. Searching a single structure used to map virtual to physical addresses to identify every data segment stored in the selected region is cumbersome and inefficient because most virtual to physical indexes are designed to quickly identify a physical address based on any possible virtual identifier within a namespace or range of possible virtual identifiers.